package demo1;

public class DynamicPlanningPractise {
    public static void main(String[] args) {
//        StringBuilder[] str = new StringBuilder[10];
//        char a = 'a';
//        str[1] = new StringBuilder();
//        str[1].append('a');
//        str[1] = new StringBuilder("a" + str[1]).append("b");
//        System.out.println(str[1]);
        StringBuilder[] str = new StringBuilder[10];
        char[] chars = new char[] {'a','g','e'};
        //1 对其进行初始化
        for(int i = 0; i < 10; i++)
            str[i] = new StringBuilder();
        str[1].append(chars[0]+chars[2]);
        str[1].insert(0,chars[1]);
        System.out.println(str[1]);
    }
//    public String longestPalindrome(String s) {
//        /**
//         通过回文子串这个题目我们可以得出：
//         我们创建一个二维的dp表便可列出该字符串中的所有回文子串
//         状态表示：
//         dp[i][j] 表示以i下标元素 j下标元素结尾的回文子串的长度
//         -若是不构成回文子串，则长度为0- i<=j
//         我们就按照回文子串的思路对其进行解题 */
//        char[] chars = s.toCharArray();
//        int n = chars.length;
//        //1 创建dp表
//        StringBuilder[][] dp = new StringBuilder[n][n];
//        //2 初始化
//        for(int i = 0; i < n; i++)
//            for(int j = 0; j < n; j++)
//                dp[i][j] = new StringBuilder();
//        //3 填表 - 从下到上开始填表
//        StringBuilder ret = new StringBuilder();
//        for(int i = n-1; i >= 0; i--) {
//            for(int j = i; j < n; j++) {
//                if(i==j) {
//                    dp[i][j] = dp[i][j].append(chars[i]);
//                } else if(i+1==j && chars[i] == chars[j]) {
//                    dp[i][j].append(chars[i]);
//                    dp[i][j].append(chars[j]);
//                } else if(chars[i] == chars[j]){
//                    if(dp[i+1][j-1])
//                }
//            }
//        }
//        //4 返回值
//        return ret.toString();
//    }

    /**
     * 最长回文子串-使用String未优化*/
    public String longestPalindromeTest(String s) {
        /**
         通过回文子串这个题目我们可以得出：
         我们创建一个二维的dp表便可列出该字符串中的所有回文子串
         状态表示：
         dp[i][j] 表示以i下标元素 j下标元素结尾的回文子串的长度
         -若是不构成回文子串，则长度为0- i<=j
         我们就按照回文子串的思路对其进行解题 */
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        String[][] dp = new String[n][n];
        //2 初始化
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dp[i][j] = "";
        //3 填表 - 从下到上开始填表
        String ret = "";
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i==j) {
                    dp[i][j]+=chars[i];
                } else if(i+1==j && chars[i] == chars[j]) {
                    dp[i][j]+=chars[i];
                    dp[i][j]+=chars[j];
                } else {
                    //两端字符相等时 需要dp[i+1][j-1]不为空
                    if(chars[i]==chars[j] && !dp[i + 1][j - 1].isEmpty()) {
                        dp[i][j] = chars[i]+dp[i+1][j-1];
                        dp[i][j]+=chars[j];
                    }
                }
                ret = ret.length()<dp[i][j].length() ? dp[i][j] : ret;
            }
        }
        //4 返回值
        return ret;
    }

    public String longestPalindrome(String s) {
        /**
         通过回文子串这个题目我们可以得出：
         我们创建一个二维的dp表便可列出该字符串中的所有回文子串
         状态表示：
         dp[i][j] 表示以i下标元素 j下标元素结尾的回文子串的长度
         -若是不构成回文子串，则长度为0- i<=j
         我们就按照回文子串的思路对其进行解题 */
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        StringBuilder[][] dp = new StringBuilder[n][n];
        //2 初始化
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dp[i][j] = new StringBuilder();
        //3 填表 - 从下到上开始填表
        StringBuilder ret = new StringBuilder();
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
//                if(i==j) {
//                    dp[i][j].append(chars[i]);
//                } else if(i+1==j && chars[i] == chars[j]) {
//                    dp[i][j].append(chars[i]);
//                    dp[i][j].append(chars[j]);
//                } else {
//                    //两端字符相等时 需要dp[i+1][j-1]不为空
//                    if(chars[i]==chars[j] && dp[i + 1][j - 1].length()!=0) {
//                        dp[i][j] = dp[i+1][j-1].insert(0,chars[i]).append(chars[j]);
//                    }
//                }
//                ret = ret.length()<dp[i][j].length() ? dp[i][j] : ret;
                if(i==j) dp[i][j].append(chars[i]);
                else if(chars[i]==chars[j]) {
                    dp[i][j] = i+1==j ? dp[i][j].insert(0,chars,i,2) :
                            dp[i+1][j-1].insert(0,chars[i]).append(chars[j]);
                ret = ret.length()<dp[i][j].length() ? dp[i][j] : ret;
                }
            }
        }
        //4 返回值
        return ret.toString();
    }

}
